// function QuickSort(arr) {
//     if (arr.length === 0) return [];
//     let index = Math.floor(arr.length / 2), pivot = arr[index], l = [], r = [], i = 0;
//     while (i < arr.length) {
//         if (i !== index) {
//             if (arr[i]<= pivot) {
//                 l.push(arr[i]);
//             } else {
//                 r.push(arr[i]);
//             }
//         }
//         i++;
//     }
//     return QuickSort(l).concat([pivot], QuickSort(r));
// }

// let arr = [2, 1, 0, 5, 4]

// console.log(QuickSort(arr));
//
// let nums = [3, 4, 5, 6, 8]
// function countTri(nums) {
//     const n = nums.length;
//     nums.sort((a, b) => a - b);
//     let ans = 0;
//     for (let i = 0; i < n; ++i) {
//         let k = i;
//         for (let j = i + 1; j < n; ++j) {
//             while (k + 1 < n && nums[k + 1] < nums[i] + nums[j]) {
//                 ++k;
//             }
//             ans += Math.max(k - j, 0);
//         }
//     }
//     return ans;
// }
// console.log(countTri(nums));

// var threeSum = function(nums) {
//     let n = nums.length, r =[];
//     if (n < 3) return r;
//     // 排序
//     nums = nums.sort((a,b) => a-b);
//     for (let i = 0; i < n; i++) {
//         // 需要和上一次枚举的数不相同
//         if (i > 0 && nums[i] === nums[i - 1]) continue;
//         // K在数组最右端
//         let k = n - 1;
//         // 需要保证 b 的指针在 c 的指针的左侧
//         for (let j = i + 1; j < n; j++) {
//             // 需要和上一次枚举的数不相同
//             if (j > i + 1 && nums[j] === nums[j - 1]) continue;
//             // 如果指针重合，随着 b 后续的增加
//             // 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
//             while (j < k && nums[i] + nums[j] + nums[k] > 0) {
//                 k--;
//             }
//             if (j === k) break;
//             if (nums[i] + nums[j] + nums[k] === 0) r.push([nums[i], nums[j], nums[k]]);
//         }
//     }
//     return r;
// };
// console.log(threeSum([-1,0,1,2,-1,-4]))
// -4,-1,-1,0,1,2
// -4 -1 1 2  1
const arr = [1,0,-1,0,-2,2],
  target = 0;
var threeSumClosest = function (nums, target) {
  let n = nums.length,
    ct = Number.MAX_SAFE_INTEGER;
  nums = nums.sort((a, b) => a - b);
  for (let i = 0; i < n; i++) {
    let j = i + 1, k = n - 1;
    while(j < k) {
        let sum = nums[i] + nums[j] + nums[k];
        if (sum === target) return target;
        if (sum > target) {
            ct = getClosestNum(sum, ct, target);
            k--;
        } else {
            ct = getClosestNum(sum, ct, target);
            j++;
        }
    }
  }
  return ct;
};

function getClosestNum(a, b, target) {
  if (Math.abs(a - target) > Math.abs(b - target)) {
    return b;
  } else {
    return a;
  }
}

// [-2, -1, 0, 0, 1, 2] 0
var fourSum = function(nums, target) {
    let n = nums.length, result = [];
    if (n < 4) return result;
    nums = nums.sort((a,b) => a-b);
    for (let i = 0; i < n - 3; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        if (sum(nums, i, i + 1, i + 2, i + 3) > target) break;
        if (sum(nums, i, n - 3, n - 2, n - 1) < target) continue;
        for (let j = i + 1; j < n - 2; j++) { 
            if (j > i + 1 && nums[j] === nums[j - 1]) continue;
            if (sum(nums, i, j, j + 1, j + 2) > target) break;
            if (sum(nums, i, j, n - 2, n - 1) < target) continue;
            let l = j + 1, r = n - 1;
            while (l < r) {
                const t = sum(nums, i, j, l, r);
                if (t === target) {
                    result.push([nums[i], nums[j], nums[l], nums[r]]);
                    while (l < r && nums[l] === nums[l + 1]) {
                        l++;
                    }
                    while (l < r && nums[r] === nums[r - 1]) {
                        r--;
                    }
                } else if (t < target) {
                    l++;
                } else {
                    r--;
                }
            }
        }
    }
    return result;
};


function sum(nums, i,j,k,m) {
    return nums[i] + nums[j] + nums[k] + nums[m];
}
console.log(fourSum(arr, target));